package com.xpu.demo;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 生成窗口最大值数组：
 * 有一个整型数组arr和一个大小为w的窗口从数组最左边滑到最右边，窗口每次先有滑动一个位置
 * 例如数组为【4,3,5,4,3,3,6,7】，窗口大小为3
 * 【4,3,5】4,3,3,6,7
 * 4【3,5,4】3,3,6,7
 * 如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口最大值
 * 实现函数：
 * 输入整型数组arr，窗口大小为w
 * 输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值
 */
public class MyArray {
    /**
     * 构建双端队列qmax，qmax存放arr下标
     * @param arr
     * @param w
     * @return
     */
    public int[] getMaxWindow(int[] arr,int w){
        if(arr==null||w<1||arr.length<w){
            return null;
        }
        LinkedList<Integer> qmax=new LinkedList<>();
        int[] res=new int[arr.length-w+1];
        int index=0;
        for (int i = 0; i < arr.length; i++) {
            while (!qmax.isEmpty()&&arr[qmax.peekLast()]<=arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if(qmax.peekFirst()==i-w){
                qmax.pollFirst();
            }
            if(i>=w-1){
                res[index++]=arr[qmax.peekFirst()];
            }
        }
        return res;
    }



    /**
     * 通过 for 循环查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */
    private  int findMaxByFor(int[] arr) {
        int max = 0; // 最大值
        for (int item : arr) {
            if (item > max) { // 当前值大于最大值，赋值为最大值
                max = item;
            }
        }
        return max;
    }
    /**
     * 根据 stream 查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */
    private  int findMaxByStream(int[] arr) {
        return Arrays.stream(arr).max().getAsInt();
    }
    /**
     * 根据 Arrays.sort 查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */
    private  int findMaxBySort(int[] arr) {
        Arrays.sort(arr);
        return arr[arr.length - 1];
    }
}
